#include "myGraph.h"
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
EdgeNode::EdgeNode()
{
    dest = -1;
    link = NULL;
}
EdgeNode::EdgeNode(int dest, EdgeNode *link)
{
    this->dest = dest;
    this->link = link;
}
EdgeNode::~EdgeNode()
{
}
int EdgeNode::getDest()
{
    return this->dest;
}
EdgeNode *EdgeNode::getNext()
{
    return this->link;
}
void EdgeNode::setDest(int dest)
{
    this->dest = dest;
}
void EdgeNode::setNext(EdgeNode *link)
{
    this->link = link;
}
VertexNode::VertexNode()
{
    data = 0;
    firstEdge = NULL;
}
VertexNode::VertexNode(char data, EdgeNode *firstEdge)
{
    this->data = data;
    this->firstEdge = firstEdge;
}
VertexNode::~VertexNode()
{
}
char VertexNode::getData()
{
    return this->data;
}
EdgeNode *VertexNode::getFirstEdge()
{
    return this->firstEdge;
}
void VertexNode::setData(char data)
{
    this->data = data;
}
void VertexNode::setFirstEdge(EdgeNode *firstEdge)
{
    this->firstEdge = firstEdge;
}
MyGraph::MyGraph()
{
    nodeNum = 0;
    edgeNum = 0;
    VexList = NULL;
}
MyGraph::MyGraph(int nodeNum, int edgeNum, char *nodeList, int *edgeStartList, int *edgeEndList)
{
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    VexList = new VertexNode[nodeNum];
    for (int i = 0; i < nodeNum; i++)
    {
        VexList[i].setData(nodeList[i]);
    }
    for (int j = 0; j < edgeNum; j++)
    {
        VexList[edgeStartList[j]].firstEdge = new EdgeNode(edgeEndList[j], VexList[edgeStartList[j]].firstEdge);
        VexList[edgeEndList[j]].firstEdge = new EdgeNode(edgeStartList[j], VexList[edgeEndList[j]].firstEdge);
    }
}
MyGraph::~MyGraph()
{

}
int MyGraph::getNodeNum()
{
    return this->nodeNum;
}
int MyGraph::getEdgeNum()
{
    return this->edgeNum;
}
string MyGraph::printGraph()
{
    string ans;
    
    for (int i = 0; i < nodeNum; i++)
    {
        string p;
        p = p + VexList[i].data + ":";
        for (EdgeNode *ads = VexList[i].firstEdge; ads != NULL; ads = ads->link)
        {
            if(ads==NULL)break;
            p = p + " " ;
            p=p+VexList[ads->dest].data;
        }
        ans = ans + p ;
        if(i!=nodeNum-1)ans=ans+"\n";
    }
    return ans;
}
void MyGraph::DFS(int v, bool *visited, string &result)
{
    result=result+(VexList[v].data);
    result=result+' ';
    for (EdgeNode *ads = VexList[v].firstEdge; ads != NULL; ads = ads->link)
    {
        if (!visited[ads->dest])
        {
            visited[ads->dest] = true;
            DFS(ads->dest, visited, result);
        }
    }
}
string MyGraph::graph_DFS_Traverse()
{
    string ans;
    bool *visit = new bool[nodeNum];
    memset(visit, 0, sizeof(visit));
    visit[0]=true;
    DFS(0, visit, ans);
    return ans;
}
void MyGraph::BFS(int v, bool *visited, string &result)
{
    queue<VertexNode> q;
    q.push(VexList[v]);
    while (!q.empty())
    {
        VertexNode su = q.front();
        result=result+q.front().data;
        result=result+" ";
        q.pop();
        for (EdgeNode *ads = su.firstEdge; ads != NULL; ads = ads->link)
        {
            if (!visited[ads->dest])
            {
                visited[ads->dest] = true;
                q.push(VexList[ads->dest]);
            }
        }
    }
}
string MyGraph::graph_BFS_Traverse()
{
    string ans;
    bool *visit = new bool[nodeNum];
    memset(visit, 0, sizeof(visit));
    visit[0]=true;
    BFS(0,visit,ans);
    return ans;
}

